A content addressable memory CAM device is a static storage device constructed of modified random access memory (RAM) cells. A CAM accelerates any application requiring fast searches of e.g., a database, list, or pattern, such as in database systems, image or voice recognition systems, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing input or selected information (i.e., data in the comparant register) against a list of pre-stored entries in the CAM memory element or array. As a result of their unique searching scheme, CAM devices are frequently employed in network equipment, particularly routers, gateways and switches, computer systems and other devices that require rapid content searching, such as routing tables for data networks or matching Internet Universal Resource Locators (URLs). Some of these tables are “learned” from the data passing through the network. Other tables are fixed tables that are loaded into the CAM by a system controller. These fixed tables reside in the CAM for a relatively long period of time. A word in a CAM is typically very large and can be 96 bits or more.
CAMs are organized differently than other memory devices (e.g., dynamic random access memory (DRAM) and static random access memory (SRAM)) in order to perform a parallel content memory search. For example, data is stored in a RAM at a particular physical location on the RAM chip, called a memory address. During a conventional RAM memory access, a user or an application supplies a memory address and data is read into or written out of the specified address. A CAM performs addressing using the content of the data rather than supplying a memory location to address stored data.
In a CAM, data is stored in locations in a somewhat random fashion. CAM storage locations can be selected by an address bus or the data can be written into the first empty memory location. Every location has one or a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found in a conventional CAM device by comparing every bit in memory with data in the comparant register. When the content stored in the CAM memory location does not match the data in the comparant register, the local match detection circuit returns a no match indication. When the content stored in the CAM memory location matches the data in the comparant register, the local match detection circuit returns a match. If one or more local match detect circuits return a match, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication. When the device is capable of returning a “match” or “no-match” indication, the device is known as a binary CAM. A CAM device with “match” “no-match” and “don't care” output is known as a ternary CAM. In addition, the CAM may return the identification of the address location in which the desired data is stored. Thus, with a CAM, the user supplies the data and gets back an address if there a match is found in the CAM memory.
Data search and table look-up performance has been improved by the introduction and development of binary and ternary CAM devices. Conventional CAM devices, however, have neither the power or space efficiency required to retrieve data by magnitude ranges. Magnitude range refers to a set of numerical values such as the numerical range of 10 to 50.
Conventional systems require a range determination using multiple comparators then a separate processing cycle to perform table look-ups to determine what action was required based on the determined range. Also, multiple processing cycles are needed in many cases to determine range data and look up actions corresponding to a range data. Also, convention systems require complicated and costly comparator designs which suffered from a variety of shortcomings. Efforts to address this shortcoming via bit masking, modification of equality comparator based CAM cells or other approaches have not been successful in improving magnitude range data retrieval, range matching and range sorting. Accordingly, there exists a need to provide improved range matching, range sorting and range based retrieval using magnitude ranges.